package cn.lena.algorithm;

import java.util.HashMap;
import java.util.Map;

//分治算法
public class Divide {

	/**求两数之和。用hashMap
	 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
	 *你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
	 */
	public static int[] twoSum(int[] nums, int target) {
	//	Map<Integer, Integer> map = new HashMap<>((int) ((float) nums.length / 0.75F + 1.0F));
		Map<Integer,Integer> map=new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			if (map.containsKey(target -  nums[i])) {
				return new int[]{map.get(target - nums[i]), i};
			}
			map.put(nums[i], i);
		}
		throw new IllegalArgumentException("No two sum value");
	}

	//匹配子序列单词数
	public static int numMatchingSubseq(String t, String[] words) {
		int i,j;
		char ii,jj;
		int num=0;int index=0;

		while(index<words.length){
			i=0;j=0;
			String s=words[index];
			if(s==null||s.equals("")) {
				num++;
				i=t.length();       //退出循环。
			}
			while(j<s.length()&&i<t.length()){
				ii=t.charAt(i);     //获取s字符串第i个字符
				jj=s.charAt(j);     //获取t字符串第j个字符
				if(ii==jj){         //字符相等
		//			System.out.println(s.length()+"----"+j);
					if(j==s.length()-1)   {
						num++;    //若此字符是s的最后一个，即true。
						i=t.length();	//跳出循环。
					}
					else { j++;i++; }     //后移一个字符
				}
				else    i++;   //t字符串后移。
			}
			index++;
		//	System.out.println("第"+(index-1)+"个字符，"+num);
		}
		System.out.println(num);
		return num;
	}

	//子序列问题：判断字符串s是否是t的子序列（是否包含在t中，按顺序但不一定要连续）。
	public boolean isSubsequence(String s, String t) {
		int i=0,j=0;
		char ii,jj;
		if(s==null||s.equals("")){
			return true;
		}
		while(j<t.length()&&i<s.length()){
			ii=s.charAt(i);     //获取s字符串第i个字符
			jj=t.charAt(j);     //获取t字符串第j个字符
			if(ii==jj){         //字符相等
				if(i==s.length()-1)   return true;    //若此字符是s的最后一个，即true。
				else { j++;i++; }     //后移一个字符
			}
			else    j++;   //t字符串后移。
		}

		return false;
	}


	//汉诺塔算法
	public static void hanoi(int num, char a, char b, char c){
		//如果只有一个盘
		if(num == 1) {
			System.out.println("第1个盘从 " + a + "->" + c);
		} else {
			//如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
			//1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
			hanoi(num - 1, a, c, b);
			//2. 把最下边的盘 A->C
			System.out.println("第" + num + "个盘从 " + a + "->" + c);
			//3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔
			hanoi(num - 1, b, a, c);
		}
	}

	//归并排序
	public static void mergeSort(int arr[]){
		int []temp = new int[arr.length];	//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
		sort(arr,0,arr.length-1,temp);
	}
	private static void sort(int[] arr,int left,int right,int []temp){
		if(left<right){			//当列表还可以继续细分的时候，继续进行细分
			int mid = (left+right)/2;
			sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
			sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
			merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
		}
	}
	private static void merge(int[] arr,int left,int mid,int right,int[] temp){
		int i = left;//左序列指针
		int j = mid+1;//右序列指针
		int t = 0;//临时数组指针
		while (i<=mid && j<=right){
			if(arr[i]<=arr[j]){
				temp[t++] = arr[i++];
			}else {
				temp[t++] = arr[j++];
			}
		}
		while(i<=mid){//将左边剩余元素填充进temp中	（此时是因为右边已经没有元素了，才跳出上一个循环）
			temp[t++] = arr[i++];
		}
		while(j<=right){//将右序列剩余元素填充进temp中
			temp[t++] = arr[j++];
		}
		t = 0;
		//将temp中的元素全部拷贝到原数组中
		while(left <= right){
			arr[left++] = temp[t++];
		}
	}

}
